import java.util.HashMap;
import java.util.Map;

/**
 * 面试题 04.12. 求和路径
 * https://leetcode-cn.com/problems/paths-with-sum-lcci/
 */
public class Solutions_mianshi_04_12 {
    public static void main(String[] args) {
//        String str = "[5 4 8 11 # 13 4 7 2 # # 5 1]";
//        int sum = 22;  // output: 3  {{5, 4, 11, 2}, {5, 8, 4, 5}, {4, 11, 7}}

        String str = "[0 1 1]";
        int sum = 1;  // output: 4  {{1}, {1}, {0, 1}, {0, 1}}

        TreeNode root = MyTreeNodeUtils.deserialize(str);
        int result = pathSum(root, sum);
        System.out.println(result);
    }

    // key：和，value：和出现的次数
    private static Map<Integer, Integer> map = null;

    /**
     * 解法二：深度优先搜索 + 前缀和（2ms）
     */
    public static int pathSum(TreeNode root, int sum) {
        res = 0;
        // map 记录前缀和
        map = new HashMap<>();
        // cur - sum = 0，时，说明该路径上的和就是等于 sum 的
        map.put(0, 1);
        dfs2(root, sum, 0);
        return res;
    }

    /**
     * 先序遍历方式，递归路径
     * @param root
     * @param sum 和
     * @param j 路径总和
     */
    public static void dfs2(TreeNode root, int sum, int j) {
        if (root == null) {
            return;
        }
        int curSum = j + root.val;
        // cur - sum 有出现过，那么存在路径的总和等于 sum，该条路径即是 cur - sum 的后一节点处
        res += map.getOrDefault(curSum - sum, 0);
        // 本次计算结果，记录到前缀和 map 中
        map.put(curSum, map.getOrDefault(curSum, 0) + 1);
        // 遍历左右子树
        dfs2(root.left, sum, curSum);
        dfs2(root.right, sum, curSum);
        // 本路径计算结果，从 map 中移除，否则遍历其他路径时，map 中冗余的结果会影响计算
        map.put(curSum, map.get(curSum) - 1);
    }

    /**
     * 解法一：深度优先搜索 + 暴力（8ms）
     */
    private static int res = 0;
    public static int pathSum2(TreeNode root, int sum) {
        res = 0;
        pathSum_temp(root, sum);
        return res;
    }

    public static void pathSum_temp(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        dfs(root, sum);
        // 左、右子节点，再作为根节点，递归
        pathSum_temp(root.left, sum);
        pathSum_temp(root.right, sum);
    }

    public static void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        sum -= root.val;
        if (sum == 0) {
            // 节点值总和为 0 的路径数量加 1
            res ++;
        }
        // 递归左、右子节点
        dfs(root.left, sum);
        dfs(root.right, sum);
    }
}
